#pragma once
#include<iostream>
using namespace std;
#include<vector>
#include<string>

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};


//模板特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

//namespace opean_address
//{
//	enum State
//	{
//		EXIST,
//		EMPTY,
//		DELETE
//	};
//
//	template<class K, class V>
//	struct HashData
//	{
//		pair<K, V> _kv;
//		State _state = EMPTY;
//	};
//
//	template<class K, class V>
//	class HashTable
//	{
//	public:
//		HashTable()
//		{
//			_tables.resize(10);//直接开10
//		}
//
//		bool Insrt(const pair<K, V>& kv)
//		{
//			if (Find(kv.first))
//			{
//				return false;//不能有相同的数
//			}
//
//			if (_n * 10 / _tables.size() >= 7)//扩容
//			{
//				HashTable<K, V> newHT;
//				newHT._tables.resize(_tables.size() * 2);
//				for (size_t i = 0; i < _tables.size(); i++)//把旧表的数据移到新表
//				{
//					if (_tables[i]._state == EXIST)//旧表的数据，插入到新表
//					{
//						newHT.Insert(_tables[i]._kv);
//					}
//				}
//				_tables.swap(newHT._tables);
//			}
//
//			//插入数据
//			size_t hashi = kv.first % _tables.size();
//			while (_tables[hashi]._state == EXIST)
//			{
//				hashi++;
//
//				hashi %= _tables.size();
//			}
//			_tables[hashi]._kv = kv;
//			_tables[hashi]._state = EXIST;
//			++_n;
//
//			return true;
//		}
//
//		HashData<K, V>* Find(const K& key)
//		{
//			size_t hashi = key % _tables.size();//先算在表中的位置
//			while (_tables[hashi]._state != EMPTY)
//			{
//				if (_tables[hashi]._state == EXIST
//					&& _tables[hashi]._kv.first == key)
//				{
//					return &_tables[hashi];
//				}
//				hashi++;
//
//				hashi = hashi % _tables.size();
//			}
//			return nullptr;
//		}
//
//		bool Erase(const K& key)
//		{
//			HashData<K, V>* ret = Find(key);
//			if (ret == nullptr)
//			{
//				return false;
//			}
//			else
//			{
//				ret->_state = DELETE;
//				return true;
//			}
//		}
//
//	private:
//		vector< HashData<K, V>> _tables;
//		size_t _n = 0;//表中存储的数据个数
//	};
//}

//namespace open_address
//{
//	enum State
//	{
//		EXIST,
//		EMPTY,
//		DELETE
//	};
//
//	template<class K, class V>
//	struct HashData
//	{
//		pair<K, V> _kv;
//		State _state = EMPTY;
//	};
//
//	template<class K, class V>
//	class HashTable
//	{
//	public:
//		HashTable()
//		{
//			_tables.resize(10);
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			if (Find(kv.first))
//			{
//				return false;
//			}
//
//			//扩容
//			if (_n * 10 / _tables.size() >= 7)
//			{
//				HashTable<K, V> newHT;
//				newHT._tables.resize(_tables.size() * 2);
//				for (size_t i = 0; i < _tables.size(); i++)
//				{
//					if (_tables[i]._state == EXIST)
//					{
//						newHT.Insert(_tables[i]._kv);
//					}
//				}
//				_tables.swap(newHT._tables);
//			}
//			//插入
//			size_t hashi = kv.first % _tables.size();
//			while (_tables[hashi]._state == EXIST)
//			{
//				++hashi;
//
//				hashi %= _tables.size();
//			}
//			_tables[hashi]._kv = kv;
//			_tables[hashi]._state = EXIST;
//			++_n;
//
//			return true;
//		}
//
//		HashData<K, V>* Find(const K& key)
//		{
//			size_t hashi = key % _tables.size();
//			while (_tables[hashi]._state != EMPTY)
//			{
//				if (_tables[hashi]._state == EXIST
//					&& _tables[hashi]._kv.first == key)
//				{
//					return &_tables[hashi];
//				}
//
//				hashi++;
//				hashi %= _tables.size();
//			}
//			return nullptr;
//		}
//
//		bool Erase(const K& key)
//		{
//			HashData<K, V>* ret = Find(key);
//			if (ret != key)
//			{
//				return false;
//			}
//			else
//			{
//				ret->_state = DELETE;
//				return true;
//			}
//		}
//
//	private:
//		vector<HashData<K, V>> _tables;
//		size_t _n = 0;
//	};
//
//}


namespace opean_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;//不允许冗余
			}

			//扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				HashTable<K, V, Hash>  newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			//插入
			//1.找到位置
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)//当前位置有数据，走下一个位置
			{
				++hashi;

				hashi %= _tables.size();
			}
			//2.进行插入
			_tables[hashi]._kv = kv;//存值
			_tables[hashi]._state = EXIST;//改状态
			++_n;//数据个数增加

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			//找到对应的位置
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];//找到返回
				}
				//一直++，直到找到
				++hashi;
				hashi %= _tables.size();
			}
			return nullptr;//没找到
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;
				return true;
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;
	};
	//不需要写析构函数
	//它有自定义类型（会调用自己的析构）和内置类型（调用浅拷贝）


	void testHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 11,21,4,14,24,15,9 };
		for (auto e : a)
		{
			ht.Insert({ e,e });
		}

		ht.Insert({ 19,19 });
		ht.Insert({ 19,191 });
		ht.Insert({ 19,190 });

		cout << ht.Find(24) << endl;
		ht.Erase(4);
		cout << ht.Find(24) << endl;
		cout << ht.Find(4) << endl;
	}

	struct StringHashFunc
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto e : s)
			{
				hash *= 31;
				hash += e;
			}
			return hash;
		}
	};

	void TestHT2()
	{
		
		HashTable<string, string, StringHashFunc> ht;
		ht.Insert({ "sort","排序" });
		ht.Insert({ "left","左边" });

		cout << StringHashFunc()("bacd") << endl;
		cout << StringHashFunc()("abcd") << endl;
		cout << StringHashFunc()("aadd") << endl;
	}
}

//namespace hash_bucket
//{
//	template<class K, class V>
//	struct HashNode
//	{
//		pair<K, V> _kv;
//		HashNode<K, V>* _next;
//
//		HashNode(const pair<K,V>& kv)
//			:_kv(kv)
//			, _next(nullptr)
//		{}
//	};
//
//	template<class K, class V, class Hash=HashFunc<K>>
//	class HashTable
//	{
//		typedef HashNode<K, V> Node;
//	public:
//
//		HashTable()
//		{
//			_tables.resize(10, nullptr);
//		}
//
//		//vector释放的时候，不会释放桶里面的数据，
//		//指针不会调用析构函数
//		~HashTable() // Node* 指针里面有一个_data需要释放
//		{
//			for (size_t i = 0; i < _tables.size(); i++)
//			{
//				Node* cur = _tables[i];
//				while (cur)
//				{
//					Node* next = cur->_next;
//					delete cur;
//					cur = next;
//				}
//				_tables[i] = nullptr;
//			}
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			Hash hs;
//			//直接挪动节点
//			size_t hashi = hs(kv.first) % _tables.size();
//			//扩容
//			if (_n == _tables.size())
//			{
//				vector<Node*> newtables(_tables.size() * 2);
//				for (size_t i = 0; i < _tables.size(); i++)
//				{
//					Node* cur = _tables[i];
//					while (cur)
//					{
//						Node* next = cur->_next;//保留下一个节点
//						size_t hashi = hs(kv.first) % _tables.size();//算出在新表的位置
//						cur->_next = newtables[hashi];//我指向桶的第一个
//						newtables[hashi] = cur;//把桶的第一个给我
//
//						cur = next;
//					}
//					_tables[i] = nullptr;//桶的第一个指向空
//				}
//				_tables.swap(newtables);
//			}
//
//			//插入
//			Node* newnode = new Node(kv);
//			newnode->_next = _tables[hashi];//链接下一个
//			_tables[hashi] = newnode;//把桶的第一个给我
//			++_n;
//
//			return true;
//		}
//
//		Node* Find(const K& key)
//		{
//			Hash hs;
//			size_t hashi = hs(key) % _tables.size();
//			Node* cur = _tables[hashi];
//			while (cur)
//			{
//				if (cur->_kv.first == key)
//				{
//					return cur;
//				}
//				cur = cur->_next;//一直沿着桶里面找
//			}
//			return nullptr;
//		}
//
//		bool Erase(const K& key)
//		{
//			size_t hashi = key % _tables.size();
//			Node* prev = nullptr;
//			Node* cur = _tables[hashi];
//			while (cur)
//			{
//				if (cur->_kv.first == key)
//				{
//					if (prev == nullptr)
//					{
//						_tables[hashi] = cur->_next;
//					}
//					else
//					{
//						prev->_next = cur->_next;
//					}
//					delete cur;
//					--_n;
//					return true;
//				}
//				prev = cur;
//				cur = cur->_next;
//			}
//			return false;
//		}
//
//
//	private:
//		vector<Node*> _tables;//本质是一个指针数值
//		size_t _n = 0;
//	};
//}

//namespace hash_bucket
//{
//	template<class K, class V>
//	struct HashNode
//	{
//		pair<K, V> _kv;
//		HashNode<K, V>* _next;
//
//		HashNode(const pair<K, V>& kv)
//			:_kv(kv)
//			, _next(nullptr)
//		{}
//	};
//
//
//	template<class K, class V, class Hash = HashFunc<K>>
//	class HashTable
//	{
//		typedef HashNode<K, V> Node;
//	public:
//		HashTable()
//		{
//			_tables.resize(10, nullptr);
//		}
//
//		~HashTable()
//		{
//			for (size_t i = 0; i < _tables.size(); i++)
//			{
//				Node* cur = _tables[i];
//				while (cur)
//				{
//					Node* next = cur->_next;
//					delete cur;
//					cur = next;
//				}
//				_tables[i] = nullptr;//桶最后指向空
//			}
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			Hash hs;
//			size_t hashi = hs(kv.first) % _tables.size();
//			//扩容
//			if (_n == _tables.size())
//			{
//				vector<Node*> newtables(_tables.size() * 2, nullptr);
//				for (size_t i = 0; i < _tables.size(); i++)//遍历旧表
//				{
//					Node* cur = _tables[i];
//					while (cur)//遍历桶里面的数据
//					{
//						Node* next = cur->_next;
//						size_t hashi = hs(cur->_kv.first) % _tables.size();//算出旧数据在新表的位置
//						//头插到新表
//						cur->_next = newtables[hashi];//我指向下一个数据
//						newtables[hashi] = cur;//第一个数据给我
//
//						cur = next;//插入完后，cur变成了next,进行链接
//					}
//					_tables[i] = nullptr;//桶的第一个指向空
//				}
//				_tables.swap(newtables);
//			}
//
//			//插入
//			Node* newnode = new Node(kv);
//			newnode->_next = _tables[hashi];
//			_tables[hashi] = newnode;
//			++_n;
//
//			return true;
//		}
//
//		Node* Find(const K& key)
//		{
//			Hash hs;
//			size_t hashi = hs(key) % _tables.size();
//			Node* cur = _tables[hashi];
//			while (cur)
//			{
//				if (cur->_kv.first == key)
//				{
//					return cur;
//				}
//				cur = cur->_next;//一直在这个桶里面找，直到找到
//			}
//			return nullptr;
//		}
//
//		bool Erase(const K& key)
//		{
//			Hash hs;
//			size_t hashi = hs(key) % _tables.size();
//			Node* prev = nullptr;
//			Node* cur = _tables[hashi];
//			while (cur)
//			{
//				if (cur->_kv.first == key)
//				{
//					if (prev == nullptr)//判断是否为桶里的第一个数据
//					{
//						_tables[hashi] = cur->_next;//指向下一个
//					}
//					else
//					{
//						prev->_next = cur->_next;// prev指向cur的下一个 
//					}
//					delete cur;
//					--_n;
//					return true;
//				}
//				prev = cur;//
//				cur = cur->_next;
//			}
//			return false;
//		}
//
//
//	private:
//		vector<Node*> _tables;
//		size_t _n = 0;
//	};
//
//	void TestHT1()
//	{
//		HashTable<int, int> ht;
//		int a[] = { 11,21,4,14,24,15,9,19,29,39 };
//		for (auto e : a)
//		{
//			ht.Insert({ e,e });
//		}
//
//		ht.Insert({ -6, 6 });
//
//		for (auto e : a)
//		{
//			ht.Erase(e);
//		}
//	}
//
//	void TestHT2()
//	{
//		HashTable<string, string> ht;
//		ht.Insert({ "sort", "排序" });
//		ht.Insert({ "left", "左边" });
//	}
//}

